//
// Created by on 2024/5/5.
//
// 查找第一个等于给定值的元素
// 查找最后一个值等于给定值的元素
// 查找第一个大于等于给定值的元素
// 查找第一个大于给定值的元素

/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个/ 最后一个值大于等于给定值的元素
 *
 * 讲解:  http://t.csdnimg.cn/uspHf
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */

#include <iostream>
#include <vector>

using namespace std;

// 查找第一个等于给定值的元素
int searchFirst(vector<int> l, int x)
{
    int left = 0, right = l.size() - 1, m;
    while (left <= right)
    {
        m = (left + right) / 2;
        if (l[m] == x)
        {
            if (m == 0 || l[m - 1] != x)
            {
                return m;
            }
            right = m - 1;
        } else if (l[m] < x)
        {
            left = m + 1;
        } else
        {
            right = m - 1;
        }
    }
    return -1;
}

// 查找最后一个值等于给定值的元素
int searchLast(vector<int> &n, int target)
{
    int l = 0, r = n.size();
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (target < n[m])
            r = m - 1;
        else if (target > n[m])
            l = m + 1;
        else
        {
            // 已经在最后一个了
            if (m + 1 > n.size() - 1 || target != n[m + 1])
                return m;
            else
                l = m + 1;
        }
    }
    return -1;
}

// 查找第一个大于等于给定值的元素
int searchFirstLargeEqual(vector<int> &n, int target)
{
    int l=0,r=n.size()-1;
    if (target>n[r-1])
        return -1;
    int mid = (l+r)/2;
    int t = r;
    while(l<=r)
    {
        mid = (l+r)/2;
        if (target<=n[mid])
        {
            t = mid;
            r=mid-1;
        } else
        {
            l=mid+1;
        }
    }
    return t;
}
int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11 12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 9};
    cout << searchFirst(l, 10) << endl;
    cout << searchLast(l, 0) << endl;
    // 查找第一个大于等于给定值的元素
    cout << searchFirstLargeEqual(l, 4) << endl;
    return 0;
}